package leecode

type NumMatrix struct {
	sums [][]int //前缀和数组
}

func Constructor304(matrix [][]int) NumMatrix {
	sums := make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		sums[i] = make([]int, len(matrix[i])+1)
	}
	//求每一行的前缀和
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			sums[i][j+1] = sums[i][j] + matrix[i][j]
		}
	}
	return NumMatrix{sums}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) (result int) {
	for row2 >= row1 {
		temp := this.sums[row2][col2+1] - this.sums[row2][col1]
		row2--
		result += temp
	}
	return result
}
